home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / cmds / tcsh / dist / tc.alloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-12-21  |  14.6 KB  |  575 lines
  1. /* $Header: /home/hyperion/mu/christos/src/sys/tcsh-6.01/RCS/tc.alloc.c,v 3.7 1991/10/28 06:26:50 christos Exp $ */
  2. /*
  3.  * tc.alloc.c (Caltech) 2/21/82
  4.  * Chris Kingsley, kingsley@cit-20.
  5.  *
  6.  * This is a very fast storage allocator.  It allocates blocks of a small
  7.  * number of different sizes, and keeps free lists of each size.  Blocks that
  8.  * don't exactly fit are passed up to the next larger size.  In this
  9.  * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  10.  * This is designed for use in a program that uses vast quantities of memory,
  11.  * but bombs when it runs out.
  12.  */
  13. /*-
  14.  * Copyright (c) 1980, 1991 The Regents of the University of California.
  15.  * All rights reserved.
  16.  *
  17.  * Redistribution and use in source and binary forms, with or without
  18.  * modification, are permitted provided that the following conditions
  19.  * are met:
  20.  * 1. Redistributions of source code must retain the above copyright
  21.  *    notice, this list of conditions and the following disclaimer.
  22.  * 2. Redistributions in binary form must reproduce the above copyright
  23.  *    notice, this list of conditions and the following disclaimer in the
  24.  *    documentation and/or other materials provided with the distribution.
  25.  * 3. All advertising materials mentioning features or use of this software
  26.  *    must display the following acknowledgement:
  27.  *    This product includes software developed by the University of
  28.  *    California, Berkeley and its contributors.
  29.  * 4. Neither the name of the University nor the names of its contributors
  30.  *    may be used to endorse or promote products derived from this software
  31.  *    without specific prior written permission.
  32.  *
  33.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  34.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  35.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  36.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  37.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  38.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  39.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  40.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  41.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  42.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  43.  * SUCH DAMAGE.
  44.  */
  45. #include "sh.h"
  46.  
  47. RCSID("$Id: tc.alloc.c,v 3.7 1991/10/28 06:26:50 christos Exp $")
  48.  
  49. char   *memtop = NULL;        /* PWP: top of current memory */
  50. char   *membot = NULL;        /* PWP: bottom of allocatable memory */
  51.  
  52. #ifndef SYSMALLOC
  53.  
  54. #undef RCHECK
  55. #undef DEBUG
  56.  
  57.  
  58. #ifndef NULL
  59. #define    NULL 0
  60. #endif
  61.  
  62. typedef unsigned char U_char;    /* we don't really have signed chars */
  63. typedef unsigned int U_int;
  64. typedef unsigned short U_short;
  65.  
  66.  
  67. /*
  68.  * The overhead on a block is at least 4 bytes.  When free, this space
  69.  * contains a pointer to the next free block, and the bottom two bits must
  70.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  71.  * byte is the size index.  The remaining bytes are for alignment.
  72.  * If range checking is enabled and the size of the block fits
  73.  * in two bytes, then the top two bytes hold the size of the requested block
  74.  * plus the range checking words, and the header word MINUS ONE.
  75.  */
  76.  
  77.  
  78. #define MEMALIGN(a) (((a) + ROUNDUP) & ~ROUNDUP)
  79.  
  80. union overhead {
  81.     union overhead *ov_next;    /* when free */
  82.     struct {
  83.     U_char  ovu_magic;    /* magic number */
  84.     U_char  ovu_index;    /* bucket # */
  85. #ifdef RCHECK
  86.     U_short ovu_size;    /* actual block size */
  87.     U_int   ovu_rmagic;    /* range magic number */
  88. #endif
  89.     }       ovu;
  90. #define    ov_magic    ovu.ovu_magic
  91. #define    ov_index    ovu.ovu_index
  92. #define    ov_size        ovu.ovu_size
  93. #define    ov_rmagic    ovu.ovu_rmagic
  94. };
  95.  
  96. #define    MAGIC        0xfd    /* magic # on accounting info */
  97. #define RMAGIC        0x55555555    /* magic # on range info */
  98. #ifdef RCHECK
  99. #define    RSLOP        sizeof (U_int)
  100. #else
  101. #define    RSLOP        0
  102. #endif
  103.  
  104.  
  105. #define ROUNDUP    7
  106.  
  107. /*
  108.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  109.  * smallest allocatable block is 8 bytes.  The overhead information
  110.  * precedes the data area returned to the user.
  111.  */
  112. #define    NBUCKETS 30
  113. static union overhead *nextf[NBUCKETS];
  114.  
  115. #ifdef notdef
  116. extern char *sbrk();
  117.  
  118. #endif
  119.  
  120. /*
  121.  * nmalloc[i] is the difference between the number of mallocs and frees
  122.  * for a given block size.
  123.  */
  124. static U_int nmalloc[NBUCKETS];
  125.  
  126. static    int    findbucket    __P((union overhead *, int));
  127. static    void    morecore    __P((int));
  128.  
  129.  
  130. #ifdef DEBUG
  131. # define CHECK(a, str, p) \
  132.     if (a) { \
  133.     xprintf(str, p);    \
  134.     xprintf("memtop = %lx membot = %lx.\n", memtop, membot);    \
  135.     abort(); \
  136.     }
  137. #else
  138. # define CHECK(a, str, p) \
  139.     if (a) { \
  140.     xprintf(str, p);    \
  141.     xprintf("memtop = %lx membot = %lx.\n", memtop, membot);    \
  142.     return; \
  143.     }
  144. #endif
  145.  
  146. memalign_t
  147. malloc(nbytes)
  148.     register size_t nbytes;
  149. {
  150. #ifndef lint
  151.     register union overhead *p;
  152.     register int bucket = 0;
  153.     register unsigned shiftr;
  154.  
  155.     /*
  156.      * Convert amount of memory requested into closest block size stored in
  157.      * hash buckets which satisfies request.  Account for space used per block
  158.      * for accounting.
  159.      */
  160. #ifdef SUNOS4
  161.     /*
  162.      * SunOS localtime() overwrites the 9th byte on an 8 byte malloc()....
  163.      * so we get one more...
  164.      * From Michael Schroeder: This is not true. It depends on the 
  165.      * timezone string. In Europe it can overwrite the 13th byte on a
  166.      * 12 byte malloc.
  167.      * So we punt and we always allocate an extra byte.
  168.      */
  169.     nbytes++;
  170. #endif
  171.  
  172.     nbytes = MEMALIGN(MEMALIGN(sizeof(union overhead)) + nbytes + RSLOP);
  173.     shiftr = (nbytes - 1) >> 2;
  174.  
  175.     /* apart from this loop, this is O(1) */
  176.     while (shiftr >>= 1)
  177.     bucket++;
  178.     /*
  179.      * If nothing in hash bucket right now, request more memory from the
  180.      * system.
  181.      */
  182.     if (nextf[bucket] == NULL)
  183.     morecore(bucket);
  184.     if ((p = (union overhead *) nextf[bucket]) == NULL) {
  185.     child++;
  186. #ifndef DEBUG
  187.     stderror(ERR_NOMEM);
  188. #else
  189.     showall(NULL, NULL);
  190.     xprintf("nbytes=%d: Out of memory\n", nbytes);
  191.     abort();
  192. #endif
  193.     /* fool lint */
  194.     return ((memalign_t) 0);
  195.     }
  196.     /* remove from linked list */
  197.     nextf[bucket] = nextf[bucket]->ov_next;
  198.     p->ov_magic = MAGIC;
  199.     p->ov_index = bucket;
  200.     nmalloc[bucket]++;
  201. #ifdef RCHECK
  202.     /*
  203.      * Record allocated size of block and bound space with magic numbers.
  204.      */
  205.     if (nbytes <= 0x10000)
  206.     p->ov_size = nbytes - 1;
  207.     p->ov_rmagic = RMAGIC;
  208.     *((U_int *) (((caddr_t) p) + nbytes - RSLOP)) = RMAGIC;
  209. #endif
  210.     return ((memalign_t) (((caddr_t) p) + MEMALIGN(sizeof(union overhead))));
  211. #else
  212.     if (nbytes)
  213.     return ((memalign_t) 0);
  214.     else
  215.     return ((memalign_t) 0);
  216. #endif                /* !lint */
  217. }
  218.  
  219. #ifndef lint
  220. /*
  221.  * Allocate more memory to the indicated bucket.
  222.  */
  223. static void
  224. morecore(bucket)
  225.     register bucket;
  226. {
  227.     register union overhead *op;
  228.     register int rnu;        /* 2^rnu bytes will be requested */
  229.     register int nblks;        /* become nblks blocks of the desired size */
  230.     register int siz;
  231.  
  232.     if (nextf[bucket])
  233.     return;
  234.     /*
  235.      * Insure memory is allocated on a page boundary.  Should make getpageize
  236.      * call?
  237.      */
  238.     op = (union overhead *) sbrk(0);
  239.     memtop = (char *) op;
  240.     if (membot == NULL)
  241.     membot = memtop;
  242.     if ((int) op & 0x3ff) {
  243.     memtop = (char *) sbrk(1024 - ((int) op & 0x3ff));
  244.     memtop += 1024 - ((int) op & 0x3ff);
  245.     }
  246.  
  247.     /* take 2k unless the block is bigger than that */
  248.     rnu = (bucket <= 8) ? 11 : bucket + 3;
  249.     nblks = 1 << (rnu - (bucket + 3));    /* how many blocks to get */
  250.     memtop = (char *) sbrk(1 << rnu);    /* PWP */
  251.     op = (union overhead *) memtop;
  252.     memtop += 1 << rnu;
  253.     /* no more room! */
  254.     if ((int) op == -1)
  255.     return;
  256.     /*
  257.      * Round up to minimum allocation size boundary and deduct from block count
  258.      * to reflect.
  259.      */
  260.     if (((U_int) op) & ROUNDUP) {
  261.     op = (union overhead *) (((U_int) op + (ROUNDUP + 1)) & ~ROUNDUP);
  262.     nblks--;
  263.     }
  264.     /*
  265.      * Add new memory allocated to that on free list for this hash bucket.
  266.      */
  267.     nextf[bucket] = op;
  268.     siz = 1 << (bucket + 3);
  269.     while (--nblks > 0) {
  270.     op->ov_next = (union overhead *) (((caddr_t) op) + siz);
  271.     op = (union overhead *) (((caddr_t) op) + siz);
  272.     }
  273.     op->ov_next = NULL;
  274. }
  275.  
  276. #endif
  277.  
  278. void
  279. free(cp)
  280.     ptr_t   cp;
  281. {
  282. #ifndef lint
  283.     register int size;
  284.     register union overhead *op;
  285.  
  286.     if (cp == NULL)
  287.     return;
  288.     CHECK(!memtop || !membot, "free(%lx) called before any allocations.", cp);
  289.     CHECK(cp > (ptr_t) memtop, "free(%lx) above top of memory.", cp);
  290.     CHECK(cp < (ptr_t) membot, "free(%lx) above top of memory.", cp);
  291.     op = (union overhead *) (((caddr_t) cp) - MEMALIGN(sizeof(union overhead)));
  292.     CHECK(op->ov_magic != MAGIC, "free(%lx) bad block.", cp);
  293.  
  294. #ifdef RCHECK
  295.     if (op->ov_index <= 13)
  296.     CHECK(*(U_int *) ((caddr_t) op + op->ov_size + 1 - RSLOP) != RMAGIC,
  297.           "free(%lx) bad range check.", cp);
  298. #endif
  299.     CHECK(op->ov_index >= NBUCKETS, "free(%lx) bad block index.", cp);
  300.     size = op->ov_index;
  301.     op->ov_next = nextf[size];
  302.     nextf[size] = op;
  303.  
  304.     nmalloc[size]--;
  305.  
  306. #else
  307.     if (cp == NULL)
  308.     return;
  309. #endif
  310. }
  311.  
  312. memalign_t
  313. calloc(i, j)
  314.     size_t  i, j;
  315. {
  316. #ifndef lint
  317.     register char *cp, *scp;
  318.  
  319.     i *= j;
  320.     scp = cp = (char *) xmalloc((size_t) i);
  321.     if (i != 0)
  322.     do
  323.         *cp++ = 0;
  324.     while (--i);
  325.  
  326.     return ((memalign_t) scp);
  327. #else
  328.     if (i && j)
  329.     return ((memalign_t) 0);
  330.     else
  331.     return ((memalign_t) 0);
  332. #endif
  333. }
  334.  
  335. #ifndef lint
  336. /* PWP: a bcopy that does overlapping extents correctly */
  337. static void
  338. mybcopy(from, to, len)
  339.     char   *from, *to;
  340.     register unsigned len;
  341. {
  342.     register char *sp, *dp;
  343.  
  344.     if (from == to)
  345.     return;
  346.     if (from < to) {
  347.     /* len is unsigned, len > 0 is equivalent to len != 0 */
  348.     for (sp = &from[len - 1], dp = &to[len - 1]; len != 0; len--, sp--, dp--)
  349.         *dp = *sp;
  350.     }
  351.     else {
  352.     /* len is unsigned, len > 0 is equivalent to len != 0 */
  353.     for (sp = from, dp = to; len != 0; len--, sp++, dp++)
  354.         *dp = *sp;
  355.     }
  356. }
  357.  
  358. #endif
  359.  
  360. /*
  361.  * When a program attempts "storage compaction" as mentioned in the
  362.  * old malloc man page, it realloc's an already freed block.  Usually
  363.  * this is the last block it freed; occasionally it might be farther
  364.  * back.  We have to search all the free lists for the block in order
  365.  * to determine its bucket: 1st we make one pass thru the lists
  366.  * checking only the first block in each; if that fails we search
  367.  * ``realloc_srchlen'' blocks in each list for a match (the variable
  368.  * is extern so the caller can modify it).  If that fails we just copy
  369.  * however many bytes was given to realloc() and hope it's not huge.
  370.  */
  371. #ifndef lint
  372. int     realloc_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
  373.  
  374. #endif                /* lint */
  375.  
  376. memalign_t
  377. realloc(cp, nbytes)
  378.     ptr_t   cp;
  379.     size_t  nbytes;
  380. {
  381. #ifndef lint
  382.     register U_int onb;
  383.     union overhead *op;
  384.     char   *res;
  385.     register int i;
  386.     int     was_alloced = 0;
  387.  
  388.     if (cp == NULL)
  389.     return (malloc(nbytes));
  390.     op = (union overhead *) (((caddr_t) cp) - MEMALIGN(sizeof(union overhead)));
  391.     if (op->ov_magic == MAGIC) {
  392.     was_alloced++;
  393.     i = op->ov_index;
  394.     }
  395.     else
  396.     /*
  397.      * Already free, doing "compaction".
  398.      * 
  399.      * Search for the old block of memory on the free list.  First, check the
  400.      * most common case (last element free'd), then (this failing) the last
  401.      * ``realloc_srchlen'' items free'd. If all lookups fail, then assume
  402.      * the size of the memory block being realloc'd is the smallest
  403.      * possible.
  404.      */
  405.     if ((i = findbucket(op, 1)) < 0 &&
  406.         (i = findbucket(op, realloc_srchlen)) < 0)
  407.     i = 0;
  408.  
  409.     onb = MEMALIGN(nbytes + MEMALIGN(sizeof(union overhead)) + RSLOP);
  410.  
  411.     /* avoid the copy if same size block */
  412.     if (was_alloced && (onb <= (U_int) (1 << (i + 3))) && 
  413.     (onb > (U_int) (1 << (i + 2))))
  414.     return ((memalign_t) cp);
  415.     if ((res = malloc(nbytes)) == NULL)
  416.     return ((memalign_t) NULL);
  417.     if (cp != res)        /* common optimization */
  418.     mybcopy(cp, res, nbytes);
  419.     if (was_alloced)
  420.     free(cp);
  421.     return ((memalign_t) res);
  422. #else
  423.     if (cp && nbytes)
  424.     return ((memalign_t) 0);
  425.     else
  426.     return ((memalign_t) 0);
  427. #endif                /* !lint */
  428. }
  429.  
  430.  
  431.  
  432. #ifndef lint
  433. /*
  434.  * Search ``srchlen'' elements of each free list for a block whose
  435.  * header starts at ``freep''.  If srchlen is -1 search the whole list.
  436.  * Return bucket number, or -1 if not found.
  437.  */
  438. static int
  439. findbucket(freep, srchlen)
  440.     union overhead *freep;
  441.     int     srchlen;
  442. {
  443.     register union overhead *p;
  444.     register int i, j;
  445.  
  446.     for (i = 0; i < NBUCKETS; i++) {
  447.     j = 0;
  448.     for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
  449.         if (p == freep)
  450.         return (i);
  451.         j++;
  452.     }
  453.     }
  454.     return (-1);
  455. }
  456.  
  457. #endif
  458.  
  459.  
  460. #else                /* SYSMALLOC */
  461.  
  462. /**
  463.  ** ``Protected versions'' of malloc, realloc, calloc, and free
  464.  **
  465.  ** On many systems:
  466.  **
  467.  ** 1. malloc(0) is bad
  468.  ** 2. free(0) is bad
  469.  ** 3. realloc(0, n) is bad
  470.  ** 4. realloc(n, 0) is bad
  471.  **
  472.  ** Also we call our error routine if we run out of memory.
  473.  **/
  474. memalign_t
  475. Malloc(n)
  476.     size_t  n;
  477. {
  478.     ptr_t   ptr;
  479.  
  480.     n = n ? n : 1;
  481.  
  482.     if ((ptr = malloc(n)) == (ptr_t) 0) {
  483.     child++;
  484.     stderror(ERR_NOMEM);
  485.     }
  486.     return ((memalign_t) ptr);
  487. }
  488.  
  489. memalign_t
  490. Realloc(p, n)
  491.     ptr_t   p;
  492.     size_t  n;
  493. {
  494.     ptr_t   ptr;
  495.  
  496.     n = n ? n : 1;
  497.     if ((ptr = (p ? realloc(p, n) : malloc(n))) == (ptr_t) 0) {
  498.     child++;
  499.     stderror(ERR_NOMEM);
  500.     }
  501.     return ((memalign_t) ptr);
  502. }
  503.  
  504. memalign_t
  505. Calloc(s, n)
  506.     size_t  s, n;
  507. {
  508.     char   *sptr;
  509.     ptr_t   ptr;
  510.  
  511.     n *= s;
  512.     n = n ? n : 1;
  513.     if ((ptr = malloc(n)) == (ptr_t) 0) {
  514.     child++;
  515.     stderror(ERR_NOMEM);
  516.     }
  517.  
  518.     sptr = (char *) ptr;
  519.     if (n != 0)
  520.     do
  521.         *sptr++ = 0;
  522.     while (--n);
  523.  
  524.     return ((memalign_t) ptr);
  525. }
  526.  
  527. void
  528. Free(p)
  529.     ptr_t   p;
  530. {
  531.     if (p)
  532.     free(p);
  533. }
  534.  
  535. #endif                /* SYSMALLOC */
  536.  
  537. /*
  538.  * mstats - print out statistics about malloc
  539.  *
  540.  * Prints two lines of numbers, one showing the length of the free list
  541.  * for each size category, the second showing the number of mallocs -
  542.  * frees for each size category.
  543.  */
  544. /*ARGSUSED*/
  545. void
  546. showall(v, c)
  547.     Char **v;
  548.     struct command *c;
  549. {
  550. #ifndef SYSMALLOC
  551.     register int i, j;
  552.     register union overhead *p;
  553.     int     totfree = 0, totused = 0;
  554.  
  555.     xprintf("tcsh current memory allocation:\nfree:\t");
  556.     for (i = 0; i < NBUCKETS; i++) {
  557.     for (j = 0, p = nextf[i]; p; p = p->ov_next, j++);
  558.     xprintf(" %4d", j);
  559.     totfree += j * (1 << (i + 3));
  560.     }
  561.     xprintf("\nused:\t");
  562.     for (i = 0; i < NBUCKETS; i++) {
  563.     xprintf(" %4d", nmalloc[i]);
  564.     totused += nmalloc[i] * (1 << (i + 3));
  565.     }
  566.     xprintf("\n\tTotal in use: %d, total free: %d\n",
  567.         totused, totfree);
  568.     xprintf("\tAllocated memory from 0x%lx to 0x%lx.  Real top at 0x%lx\n",
  569.         membot, memtop, (char *) sbrk(0));
  570. #else
  571.     xprintf("Allocated memory from 0x%lx to 0x%lx (%ld).\n",
  572.         membot, memtop = (char *) sbrk(0), memtop - membot);
  573. #endif                /* SYSMALLOC */
  574. }
  575.